package com.kevin.Code.LinkNode;

/**
 * @author Vinlee Xiao
 * @Classname OddEvenLinkedlist
 * @Description Leetcode 328. 奇偶链表 中等难度
 * @Date 2021/12/18 10:26
 * @Version 1.0
 */
public class OddEvenLinkedlist {

    /**
     * 奇偶链表 原地移动
     *
     * @param head
     * @return
     */
    public ListNode oddEvenList(ListNode head) {

        //处理特殊情况
        if (head == null || head.next == null) {
            return head;
        }

        ListNode move = head;
        //奇数的头结点
        ListNode oddHead = new ListNode(-1);
        oddHead.next = head;
        ListNode oddMove = oddHead;
        //偶数结点的头结点
        ListNode evenHead = new ListNode(-1);
        evenHead.next = null;
        ListNode evenMove = evenHead;

        while (move != null) {

            //先处理奇数
            oddMove.next = move;
            oddMove = oddMove.next;
            //处理偶数 move再移动一步
            //将奇数结点的最后一个结点连接到偶数的头结点
            if (move.next == null) {
                oddMove.next = evenHead.next;
                return oddHead.next;
            }
            //move向后再移动一次
            move = move.next;
            //将奇数尾部连接置为0
            oddMove.next = null;

            //偶数的尾部连接指向当前结点
            evenMove.next = move;
            move = move.next;

            evenMove = evenMove.next;
            evenMove.next = null;

        }
        //
        oddMove.next = evenHead.next;


        return oddHead.next;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);


        node1.next = node2;
        node2.next = node3;


        OddEvenLinkedlist oddEvenLinkedlist = new OddEvenLinkedlist();
        ListNode node = oddEvenLinkedlist.oddEvenList(node1);
        int cnt = 0;
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;


        }
    }
}
